<?php
/*
 * 边界都是1的最大正方形大小
 * 【题目】
 * 给定一个NN的矩阵matrix，在这个矩阵中，只有0和1两种值，返回边框全是1的最大正方形的边长长度。
 * 例如：
 * 0 1 1 1 1
 * 0 1 0 0 1
 * 0 1 0 0 1
 * 0 1 1 1 1
 * 0 1 0 1 1
 * 其中，边框全是1的最大正方形的大小为4*4，所以返回4。
 */
$matrix = [
    [0, 1, 1, 1, 1],
    [0, 1, 0, 0, 1],
    [0, 1, 0, 0, 1],
    [0, 1, 1, 1, 1],
    [0, 1, 0, 1, 1],
];
$obj    = new Code_04_MaxOneBorderSize();
echo $obj->main($matrix);

class Code_04_MaxOneBorderSize
{
    /*
     * 一个矩阵如果是N*N的话，
     * 他的子矩阵的数量级是O(n^4)（左上角的点和右小角的点确立子矩阵大小，左上角的点是O(n^2)，右下角的点是O(n^2)
     * 子矩阵中是正方形的是O(n^3)（左上角的点是O(n^2)，右下角的点就是从1-N的范围就是O(n)
     *
     * 准备两个预处理数组：
     * 1、down数组， 记录matrix[i][j]点里包括自己在内【往下】数有几个连续的1
     * 2、right数组，记录matrix[i][j]点里包括自己在内【往右】数有几个连续的1
     * 3、枚举每一个正方形，正方形左上角的点(i,j)，假设边长为k。查看对应right和down数组里的值是否满足要求
     * 左上角的点：right>=k, down>=k；
     * 右上角的点：down>=k;
     * 左下角的点：right>=k;
     */
    public function main($matrix)
    {
        list($down, $right) = $this->_initHelpMatrix($matrix);
        $rows = count($matrix);
        $cols = count($matrix[0]);
        for ($size = min($rows, $cols); $size > 0; $size--) {
            if ($this->_hasSizeOfBorder($size, $right, $down)) {
                return $size;
            }
        }
        return 0;
    }

    // 生成预处理数组down和right
    protected function _initHelpMatrix($matrix)
    {
        $rows = count($matrix);
        $cols = count($matrix[0]);
        $down = array_fill(0, $rows, array_fill(0, $cols, 0));
        $right = array_fill(0, $rows, array_fill(0, $cols, 0));
        // 从右下往左上生成预处理数组
        if ($matrix[$rows - 1][$cols - 1] == 1) {
            $right[$rows - 1][$cols - 1] = 1;
            $down[$rows - 1][$cols - 1] = 1;
        }
        // 最右列
        for ($i = $rows - 2; $i != -1; $i--) {
            if ($matrix[$i][$cols - 1] == 1) {
                $right[$i][$cols - 1] = 1;
                $down[$i][$cols - 1] = $down[$i + 1][$cols - 1] + 1;
            }
        }
        // 最后一行
        for ($i = $cols - 2; $i != -1;  $i--) {
            if ($matrix[$rows - 1][$i] == 1) {
                $right[$rows - 1][$i] = $right[$rows - 1][$i + 1] + 1;
                $down[$rows - 1][$i] = 1;
            }
        }
        // 生成其他单元格的数据，down从下到上，right从右到左
        for ($i = $rows -2; $i != -1; $i--) {
            for ($j = $cols -2; $j != -1; $j--) {
                if ($matrix[$i][$j] == 1) {
                    $right[$i][$j] = $right[$i][$j + 1] + 1;
                    $down[$i][$j] = $down[$i + 1][$j] + 1;
                }
            }
        }
        return [$down, $right];
    }

    protected function _hasSizeOfBorder($size, $right, $down)
    {
        for ($i = 0; $i != count($right) - $size + 1; $i++) {
            for ($j = 0; $j != count($right[0]) - $size + 1; $j++) {
                if (
                    $right[$i][$j] >= $size
                    &&
                    $down[$i][$j] >= $size
                    &&
                    $right[$i + $size - 1][$j] >= $size
                    &&
                    $down[$i][$j + $size - 1] >= $size
                ) {
                    return true;
                }
            }
        }
        return false;
    }

}